Search Results

1. S. Aalto, U. Ayesta and R. Righter, On the Gittins index in the M/G/1 queue, Queueing Systems, vol. 63, pp. 437-458, 2009 (link)(bib)

   Abstract: For an M/G/1 queue with the objective of minimizing the mean number of jobs in the system, the Gittins index rule is known to be optimal among the set of non-anticipating policies. We develop properties of the Gittins index, and extend the optimality result to minimize the mean holding costs for multi-class queues. For a single-class queue it is known that when the service time distribution is of type Decreasing Hazard Rate (New Better than Used in Expectation), the Foreground-Background (First-Come-First-Served) discipline is optimal. By utilizing the Gittins index approach, we show that in fact, FB and FCFS are optimal if and only if the service time distribution is of type DHR and NBUE, respectively. For the multi-class case, we obtain new results that characterize the optimal policy under various assumptions on the service time distributions.